; iterative exponentiation procedure

; the recursive procedure
(define (fast-expt b n)
   (cond ((= n 0) 1)
         ((even? n) (square (fast-expt b (/ n 2))))
         (else (* b (fast-expt b (- n 1))))))

(define (square x) (* x x))

(define (even? n)
   (= (remainder n 2) 0))

(define (expt base n)
  (expt-iter base n 1))

(define (dec x) (- x 1))

; the invariant here is that result = (base^n)*a
(define (expt-iter base n a)
  (cond ((= n 0) a)
        ((even? n) (expt-iter (square base) (/ n 2) a))
        (else (expt-iter base (dec n) (* base a)))))